47. 全排列 II

Similar Question

Solution Tips

方案一: 回溯 + N 叉树 + 跳过重复

var permuteUnique = function (nums) {
    const res = [];
    // 因为是全排列, 所以顺序无所谓, 可以排序之后处理跳过重复
    // 如果不排序的话, 也可以参考 491 去重? 因为总会有 pop 然后 push 重复的那一刻, skip 即可跳过重复
    // 好像 N 叉树的思路, 是不能用 trick skip 的? 那还是乖乖记录单层的 used 吧
    nums.sort((a, b) => a - b)
    dfs([], nums);
    return res;

    function dfs(chosen, rest, curIndex) {
        if (chosen.length === nums.length) {
            res.push([...chosen])
            return;
        }

        // index 每次都是从 0 开始, 所以二元思路好像不太好处理?
        for (let i = 0; i < rest.length; i++) {
            chosen.push(rest[i])
            const newRest = rest.slice(0, i).concat(rest.slice(i + 1));
            dfs(chosen, newRest);
            chosen.pop();

            while(rest[i] === rest[i+1]) i++
        }
    }
}
console.log(permuteUnique([1,2,3,3]))

方案二: 回溯 + 二元思路

没做出来...

怎么才能运用上 491 的去重思路呢?